package 困难;

/**
 * 对于正整数 x，如果区间 [1,x-1]内的所有数字都已经被覆盖，
 * 且 x 在数组中，则区间 [1,2x-1] 内的所有数字也都被覆盖。证明如下。
 *
 * 对于任意 1≤y<x，y已经被覆盖，x 在数组中，因此 y+x 也被覆盖，
 * 区间 [x+1,2x-1]即区间 [1,x-1]内的每个数字加上 x 之后得到的区间）内的所有数字也被覆盖，
 * 由此可得区间 [1,2x-1] 内的所有数字都被覆盖。
 *
 * 假设数字 x 缺失，则至少需要在数组中补充一个小于或等于 x 的数，才能覆盖到 x，否则无法覆盖到 x。
 *
 * 如果区间 [1,x−1] 内的所有数字都已经被覆盖，则从贪心的角度考虑，补充 x 之后即可覆盖到 x，
 * 且满足补充的数字个数最少。在补充 x 之后，区间 [1,2x-1]内的所有数字都被覆盖，下一个缺失的数字一定不会小于 2x。
 *
 * 由此可以提出一个贪心的方案。每次找到未被数组 nums 覆盖的最小的整数 x，
 * 在数组中补充 x，然后寻找下一个未被覆盖的最小的整数，重复上述步骤直到区间 [1,n] 中的所有数字都被覆盖。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 按要求补齐数组 {

    public static void main(String[] args) {

    }


    public static int minPatches(int[] nums, int n){
        long x = 1;//前index个数字的边界
        int patches = 0;//添加的数字的个数
        int index = 0;
        while (x<=n){
            if (index<nums.length && nums[index]<=x){
                x += nums[index];
                index++;
            }else {
                x *= 2;
                patches++;
            }
        }
        return patches;
    }
}
